package org.example.leetcode;
import java.util.*;
/**
 * @version 1.0.0
 * @author: lynn
 * @description: 包含重复数字的数组 nums ，返回其 所有可能的全排列
 *
 * @date: 2021/7/26 14:28
 */
public class LC47 {
    public static void main(String[] args) {
       LC47 lc=new LC47();
       int[] nums={1,0,1};
       System.out.println(lc.permuteUnique(nums));
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        if (nums.length==0||nums==null) return new ArrayList<>(res);
        List<Integer> tmpList=new ArrayList<>();
        int[] v=new int[nums.length];
        Arrays.sort(nums);
        backTrack(nums,v,tmpList,res);
        return  new ArrayList<>(res);
    }
    //fixme 执行过程 https://www.bilibili.com/video/BV11T4y1c7ch?from=search&seid=12097332927703753072
    private void backTrack(int[] nums,int[] v,List<Integer> list,List<List<Integer>> res){
        if (list.size()==nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i <nums.length ; i++) {
            if (v[i]==1) continue;
            //fixme 控制输出不重复,前提是Arrays.sort  int[] nums={1,0,1};
            if (i>0 && nums[i]==nums[i-1] && v[i-1] ==1) continue;
            v[i]=1;
            list.add(nums[i]);
            backTrack(nums,v,list,res);
            list.remove(list.size()-1);
            v[i]=0;
        }
    }
}
